package leetcode_100;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *LongestSubstringWithoutRepeatingCharacters_3 不含重复字符的最大子串
 *describe:用滑动窗口法 AC 30%
 *2018年12月17日 上午10:56:28
 */
public class LongestSubstringWithoutRepeatingCharacters_3 {
	public static void main(String[] args) {
		LongestSubstringWithoutRepeatingCharacters_3 test=new LongestSubstringWithoutRepeatingCharacters_3();
		System.out.println(test.lengthOfLongestSubstring("abba"));
	}
	
	public int lengthOfLongestSubstring(String s) {
		if(s==null||s.length()==0) return 0;
        int left=-1,max=0;
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        char []chars=s.toCharArray();
        for(int i=0;i<s.length();++i) {
        	if(map.containsKey(chars[i])) {
        		if(map.get(chars[i])>=left)
        			left=map.get(chars[i]);
        	}
        	map.put(chars[i], i);
        	max=Math.max(max,i-left);
        }
        return max;
    }
}
